package com.zm.demo.core.leetcode;

import java.util.ArrayList;
import java.util.List;

import static java.lang.System.out;

/**
 * Created by Administrator on 2020/1/11.
 */
public class IsBalanced {

    Integer maxDep= Integer.MIN_VALUE;
    Integer minDep = Integer.MAX_VALUE;
    public boolean isBalanced(TreeNode root) {
        if (root == null){
            return true;
        }
        isBalanced1(root, 1);
        return Math.abs(maxDep - minDep) <= 1;
    }

    public void isBalanced1(TreeNode root, int level) {
        if (root == null){
            return;
        }

        if (root.left == null || root.right == null){
            maxDep = Math.max(maxDep, level);
            minDep = Math.min(minDep, level);
        }
        if (root.left != null || root.right != null){
            isBalanced1(root.left, level+1);
            isBalanced1(root.right, level+1);
        }
    }


    public int[] getNoZeroIntegers(int n) {

        int first= 1;
        int second;
        while(first<n){
            while(String.valueOf(first).indexOf('0')!=-1){
                first++;
            }
            second = n - first;
            if(String.valueOf(second).indexOf('0') ==-1){
                return new int[]{first, second};
            }else {
                first++;
            }

        }
        return null;
    }

    public static int minFlips(int a, int b, int c) {
        String aStr = Integer.toBinaryString(a);
        String bStr = Integer.toBinaryString(b);
        String cStr = Integer.toBinaryString(c);

        int[][]ary = new int[3][32];
        int aLenth = aStr.length()-1;
        for (int j = 31; j >= 0 && aLenth>=0;  j--, aLenth--) {
            ary[0][j] = Integer.valueOf(String.valueOf(aStr.charAt(aLenth)));
        }
        int bLenth = bStr.length()-1;
        for (int j = 31; j >= 0 && bLenth>=0;  j--, bLenth--) {
            ary[1][j] = Integer.valueOf(String.valueOf(bStr.charAt(bLenth)));;
        }
        int cLenth = cStr.length()-1;
        for (int j = 31; j >= 0 && cLenth>=0;  j--, cLenth--) {
            ary[2][j] = Integer.valueOf(String.valueOf(cStr.charAt(cLenth)));
        }

        int count=0;
        for (int j = ary[0].length-1; j >=0 ; j--) {
            if (ary[2][j] == 0){
                if (ary[0][j] != 0){
                    count++;
                }
                if (ary[1][j] != 0){
                    count++;
                }
            }
            if (ary[2][j] == 1){
                if (ary[0][j] == 0 && ary[1][j] == 0){
                    count++;
                }

            }
        }

        return count;
    }

    /**
     * 4
     [[0,1],[0,2],[1,2]]
     * @param n
     * @param connections
     * @return
     */
    public static int makeConnected(int n, int[][] connections) {

        int more=0;
        int connected = 2;
        for (int j = 0; j < n ; j++) {
            boolean isConnetcted = false;
            for (int i = 0; i < connections.length; i++) {
                if (connections[i][1] == j){
                    if (isConnetcted){
                        connected++;
                    }else {
                        isConnetcted= true;
                    }
                }
            }
        }

        int need = n-connected;
        if (need <= 0 ){
            return 0;
        }else if (more >= need){
            return need;
        }else {
            return -1;
        }
    }

    public static void main(String[] args){
//        out.println(makeConnected(4, new int[][]{{0,1},{0,2},{1,2},}));
        out.println(Long.valueOf(1));
    }
}
